const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D",
    },
    right: {
      val: "E",
    },
  },
  right: {
    val: "C",
    right: {
      val: "F",
    },
  },
};
// 左 - 根 - 右
// 递归方式
// 所有遍历函数的入参都是树的根结点对象
function inorder(root) {
  // 递归边界，root 为空
  if (!root) {
    return;
  }

  // 递归遍历左子树
  inorder(root.left);
  // 输出当前遍历的结点值
  console.log("当前遍历的结点值是：", root.val);
  // 递归遍历右子树
  inorder(root.right);
}
inorder(root);

// 迭代方式
/**
 * 思路分析
 * 根结点不再出现在遍历序列的边界、而是出现在遍历序列的中间。
 * 这就意味着无论如何我们不能再将根结点作为第一个被 pop 出来的元素来处理了——出栈的时机被改变了，这意味着入栈的逻辑也需要调整。
 */

const inorderTraversal = function (root) {
  // 定义结果数组
  const res = [];
  // 初始化栈结构
  const stack = [];
  // 用一个 cur 结点充当游标
  let cur = root;
  // 当 cur 不为空、或者 stack 不为空时，重复以下逻辑
  while (cur || stack.length) {
    // 这个 while 的作用是把寻找最左叶子结点的过程中，途径的所有结点都记录下来
    while (cur) {
      // 将途径的结点入栈
      stack.push(cur);
      // 继续搜索当前结点的左孩子
      cur = cur.left;
    }
    // 取出栈顶元素
    cur = stack.pop();
    // 将栈顶元素入栈
    res.push(cur.val);
    // 尝试读取 cur 结点的右孩子
    cur = cur.right;
  }
  // 返回结果数组
  return res;
};

console.log(inorderTraversal(root));